package history.hot100;

// 337. 打家劫舍 III
public class LeetCode_337 {
    public int rob(TreeNode root) {
        int []rootState = dfs(root);
        return Math.max(rootState[0], rootState[1]);
    }

    public int [] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int []l = dfs(node.left);
        int []r = dfs(node.right);
        int selected = node.val + l[1]+r[1];
        int notSelected = Math.max(l[0], l[1])+Math.max(r[0], r[1]);
        return new int[] {selected, notSelected};
    }
}
